/**
 * 堆排序算法
 * @author firebroo
 *
 */
class Heap{
	public void heapsort(int[] data){
		int temp;
		for(int i=(data.length >> 1) -1;i >=0;--i){
			moveDown(data,i,data.length-1);
		}
		for(int i=data.length-1;i>=1;--i){
			temp=data[0];
			data[0]=data[i];
			data[i]=temp;
			moveDown(data,0,i-1);
		}
	}
	
	/**
	 *堆组织 
	 */
	public void moveDown(int[] data,int first,int last){
		int largest=(first << 1) + 1;
		int temp;
		while(largest<=last){
			if(largest<last && data[largest]<data[largest+1]){
				largest++;
			}
			if(data[first]<data[largest]){
				temp=data[first];
				data[first]=data[largest];
				data[largest]=temp;
				first=largest;
				largest=(first << 1) + 1;
			}
			else{
				largest=last+1;
			}
		}
	}
}

/**
 *堆排序算法测试 
 */
public class HeapSort {
	public static void main(String[] args){
		int[] data={1,22,3,55,4};
		Heap test=new Heap();
		test.heapsort(data);
		for(int i=0;i<data.length;i++){
			System.out.println(data[i]);
		}
	}
}
